# 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
# 返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None


# 返回 RandomListNode
# 用字典保存random的映射关系就可以了，next可以用数组顺着来
def Clone(self, pHead):
    p1 = pHead
    nodes = []
    d = {}
    while p1:
        nodes.append(p1)
        p1 = p1.next
    p1 = pHead  # 遍历过一次之后，再把他从头开始，为下一次遍历做准备
    while p1:
        if p1.random:
            d[nodes.index(p1)] = nodes.index(p1.random)  # 这存储的是每一个下标对应的random节点下标d{pos:random_pos}
        else:
            d[nodes.index(p1)] = -1
        p1 = p1.next
    newNodes = [RandomListNode(x.label) for x in nodes]
    for i, node in enumerate(newNodes):
        if i < len(newNodes) - 1:
            node.next = newNodes[i + 1]
        if d[i] != -1:
            node.random = newNodes[d[i]]

    return newNodes[0] if newNodes else None
